#include <stdio.h>
#include <string.h>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

#define TRACE(x...) 
#define PRINT(x...) TRACE(printf(x))

#define INF 0x3f3f3f3f

#define rep(i,n) for (int i=0; i<n; i++)

int n;
int r;
char tmp1[50], tmp2[50];
int w;
map<string, int> m;
int graph[210][210];
int cont;
string str1, str2;
int test;

int main() {
	test=0;

	while (1) {
		m.clear();
		scanf("%d %d", &n ,&r);
		test++;

		if (!n && !r) break;
		cont=0;

		rep(i,n) rep(j,n) graph[i][j]=-1;

		rep(i,r) {
			scanf(" %s %s %d", tmp1, tmp2, &w);	

			if (m.find(tmp1)==m.end()) {
				m[tmp1]=cont++;
			}
			
			if (m.find(tmp2)==m.end()) {
				m[tmp2]=cont++;
			}

			graph[m[tmp1]][m[tmp2]]=graph[m[tmp2]][m[tmp1]]=w;
		}

		TRACE(
			rep(i,n) {
				rep(j,n) printf("%d ", graph[i][j]);
				printf("\n");
			}
			
			printf("\n");
		)

		scanf(" %s %s", tmp1, tmp2);

		rep(k,n) rep(i,n) rep(j,n) graph[i][j] = max(graph[i][j], min(graph[i][k], graph[k][j]));

		TRACE(
			rep(i,n) {
				rep(j,n) printf("%d ", graph[i][j]);
				printf("\n");
			}
			
			printf("\n");
		)

		printf("Scenario #%d\n", test);
		printf("%d tons\n\n", graph[m[tmp1]][m[tmp2]]); 
	}

	return 0;
}
